/**
 * 300. 最长递增子序列
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/
 */

/**
 * @param {number[]} nums
 * @return {number}
 */
function lengthOfLIS(nums) {
  const dp = new Array(nums.length).fill(1);
  let max = 1;
  for (let i = 1; i < nums.length; i += 1) {
    let count = 0;
    for (let j = 0; j < i; j += 1) {
      if (nums[j] < nums[i] && dp[j] > count) {
        count = dp[j];
      }
    }
    count += 1;
    if (count > max) {
      max = count;
    }
    dp[i] = count;
  }
  return max;
}

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]) === 4);
console.log(lengthOfLIS([0, 1, 0, 3, 2, 3]) === 4);
console.log(lengthOfLIS([7, 7, 7, 7, 7, 7, 7]) === 1);
